#include <stdio.h>
#include <list>
#include <map>
#include <string>
#include <iostream>

using namespace std;

class node{
	public:
		node(string n){
			leastCostWeight = 100;
			name = n;
			visited = false;
			leastCodeNode = 0;
		}
		~node(){
		}

		int leastCostWeight;
		node* leastCodeNode;

		list<node*> branches;
		string name;
		map<string, int> weight;
		bool visited;

};

void createMap(map<string, node*> &nMap){
	nMap["a"] = new node("a");	
	nMap["b"] = new node("b");	
	nMap["c"] = new node("c");	
	nMap["d"] = new node("d");	
	nMap["e"] = new node("e");	
	nMap["f"] = new node("f");	

	nMap["a"]->branches.push_back(nMap["b"]);
	nMap["a"]->branches.push_back(nMap["c"]);
	nMap["a"]->branches.push_back(nMap["e"]);
	nMap["a"]->weight["a"] = 0;
	nMap["a"]->weight["b"] = 1;
	nMap["a"]->weight["c"] = 1;
	nMap["a"]->weight["e"] = 2;
	nMap["a"]->leastCostWeight = 0;
	nMap["a"]->leastCodeNode = 0;


	nMap["b"]->branches.push_back(nMap["a"]);
	nMap["b"]->branches.push_back(nMap["c"]);
	nMap["b"]->branches.push_back(nMap["d"]);
	nMap["b"]->weight["a"] = 1;
	nMap["b"]->weight["c"] = 1;
	nMap["b"]->weight["d"] = 2;


	nMap["c"]->branches.push_back(nMap["a"]);
	nMap["c"]->branches.push_back(nMap["b"]);
	nMap["c"]->branches.push_back(nMap["d"]);
	nMap["c"]->branches.push_back(nMap["f"]);
	nMap["c"]->weight["a"] = 1;
	nMap["c"]->weight["b"] = 1;
	nMap["c"]->weight["d"] = 1;
	nMap["c"]->weight["f"] = 1;


	nMap["d"]->branches.push_back(nMap["b"]);
	nMap["d"]->branches.push_back(nMap["c"]);
	nMap["d"]->branches.push_back(nMap["f"]);
	nMap["d"]->weight["b"] = 2;
	nMap["d"]->weight["c"] = 1;
	nMap["d"]->weight["f"] = 1;


	nMap["e"]->branches.push_back(nMap["a"]);
	nMap["e"]->branches.push_back(nMap["f"]);
	nMap["e"]->weight["a"] = 2;
	nMap["e"]->weight["f"] = 1;


	nMap["f"]->branches.push_back(nMap["e"]);
	nMap["f"]->branches.push_back(nMap["c"]);
	nMap["f"]->branches.push_back(nMap["d"]);
	nMap["f"]->weight["e"] = 1;
	nMap["f"]->weight["c"] = 1;
	nMap["f"]->weight["d"] = 1;

}

void findShortestPath(map<string, node*> & nodeMap, string des){

	map<string, node*>::iterator it;
	list<node*>::iterator lItr;

	for(it = nodeMap.begin(); it != nodeMap.end(); it++){
		for(lItr = it->second->branches.begin(); lItr != it->second->branches.end();lItr++){
			string branchName = (*lItr)->name;
			int totalCost = it->second->leastCostWeight + it->second->weight[branchName];
			int wt = nodeMap[branchName]->leastCostWeight;

			if(totalCost < wt){
				nodeMap[branchName]->leastCostWeight = totalCost;
				nodeMap[branchName]->leastCodeNode = it->second;
			}
		}
	}

	node* prevNode = nodeMap[des]->leastCodeNode;

	string output = des;
	while(prevNode != 0){
		output = prevNode->name + "->" + output;
		cout << output << endl;
		prevNode = prevNode->leastCodeNode;
	}
}

int main(){
	map<string, node*> nodeMap;
	map<string, node*>::iterator i;
	createMap(nodeMap);

	findShortestPath(nodeMap, "e");

	for(i = nodeMap.begin(); i != nodeMap.end(); i++){
		if(i->second->leastCodeNode != 0){
			cout << i->first << "\t" << i->second->leastCodeNode->name << "\t" << i->second->leastCostWeight << endl;
		}
	}

	return 0;
}
